import java.util.HashSet;

public class WordLadder {

	public boolean isNeighbour(String a, String b) {
		if (a.length() != b.length()) {
			return false;
		}
		int cnt = 0;
		for (int i = 0; i < a.length(); ++i) {
			if (a.charAt(i) != b.charAt(i)) {
				cnt++;
			}
			if (cnt == 2)
				return false;
		}
		if (cnt == 1)
			return true;
		return false;
	}

	public int ladderLength(String start, String end, HashSet<String> dict) {
		String q[] = new String[dict.size() + 2];
		int dep[] = new int[dict.size() + 2];
		HashSet<String> visit = new HashSet<String>();
		int head = 0, rear = -1;
		q[++rear] = start;
		dep[rear] = 2;
		visit.add(start);
		while (head <= rear) {
			String u = q[head];
			int d = dep[head++];
			if (isNeighbour(u, end)) {
				return d;
			}
			for (int i = 0; i < u.length(); ++i) {
				char[] c = u.toCharArray();
				for (int j = 0; j < 26; ++j) {
					if ((char) ('a' + j) == u.charAt(i)) {
						continue;
					}
					c[i] = (char) ('a' + j);
					String v = new String(c);
					if (dict.contains(v) && !visit.contains(v)) {
						visit.add(v);
						q[++rear] = v;
						dep[rear] = d + 1;
					}
				}
			}
		}
		return 0;
	}
}
